{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum of an Hourglass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #沙漏的最大总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的整数矩阵 <code>grid</code> 。</p>\n",
    "\n",
    "<p>按以下形式将矩阵的一部分定义为一个 <strong>沙漏</strong> ：</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/08/21/img.jpg\" style=\"width: 243px; height: 243px;\">\n",
    "<p>返回沙漏中元素的 <strong>最大</strong> 总和。</p>\n",
    "\n",
    "<p><strong>注意：</strong>沙漏无法旋转且必须整个包含在矩阵中。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/08/21/1.jpg\" style=\"width: 323px; height: 323px;\">\n",
    "<pre><strong>输入：</strong>grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]\n",
    "<strong>输出：</strong>30\n",
    "<strong>解释：</strong>上图中的单元格表示元素总和最大的沙漏：6 + 2 + 1 + 2 + 9 + 2 + 8 = 30 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/08/21/2.jpg\" style=\"width: 243px; height: 243px;\">\n",
    "<pre><strong>输入：</strong>grid = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "<strong>输出：</strong>35\n",
    "<strong>解释：</strong>上图中的单元格表示元素总和最大的沙漏：1 + 2 + 3 + 5 + 7 + 8 + 9 = 35 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>3 &lt;= m, n &lt;= 150</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-of-an-hourglass](https://leetcode.cn/problems/maximum-sum-of-an-hourglass/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-of-an-hourglass](https://leetcode.cn/problems/maximum-sum-of-an-hourglass/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]]', '[[1,2,3],[4,5,6],[7,8,9]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "            grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "            for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(1, m-1):\n",
    "            for j in range(1, n-1):\n",
    "                ans = max(grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1] + grid[i][j] + grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1], ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(0,m-2):\n",
    "            for j in range(0,n-2):\n",
    "                ans = max(ans,grid[i][j]+grid[i][j+1]+grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i-1>=0 and i+1 <m and j-1 >=0 and j+1<n:\n",
    "                    t = grid[i][j]\n",
    "                    t += grid[i-1][j-1] + grid[i-1][j] + grid[i-1][j+1]\n",
    "                    t += grid[i+1][j-1] + grid[i+1][j] + grid[i+1][j+1]\n",
    "\n",
    "                    ret = max(ret, t)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ans=0\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                c=grid[i][j]+grid[i][j+1]+grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2]\n",
    "                ans=max(ans,c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(1,m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                num = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] + grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                ans = max(ans, num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = -float('inf')\n",
    "        for i in range(m-2):\n",
    "            temp = grid[i][0] + grid[i][1] + grid[i][2] + grid[i+1][1] + sum(grid[i+2][0:3])\n",
    "            ans = max(ans, temp)\n",
    "            for j in range(3, n):\n",
    "                temp -= grid[i][j-3] + grid[i+2][j-3] + grid[i+1][j-2] - grid[i][j] - grid[i+2][j] - grid[i+1][j-1]\n",
    "                ans = max(ans, temp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n =len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(1,m-1):\n",
    "            for j in range(1,n-1):\n",
    "                sum1 = grid[i-1][j-1]+grid[i-1][j]+grid[i-1][j+1]\n",
    "                sum2 = grid[i][j]\n",
    "                sum3 = grid[i+1][j-1]+grid[i+1][j]+grid[i+1][j+1]\n",
    "                res = max(res,sum1+sum2+sum3)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for row in range(len(grid)-2):\n",
    "            for col in range(len(grid[0])-2):\n",
    "                hourglass = sum(grid[row][col:col+3]) + grid[row+1][col+1] + sum(grid[row+2][col:col+3])\n",
    "                ans = max(ans, hourglass)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(2, m):\n",
    "            temp = grid[i - 2][0] + grid[i - 2][1] + grid[i - 2][2] + grid[i - 1][1] + grid[i][0] + grid[i][1] + grid[i][2]\n",
    "            ans = max(ans, temp)\n",
    "            for j in range(3, n):\n",
    "                temp += grid[i - 2][j] + grid[i][j] + grid[i - 1][j - 1] - grid[i - 2][j - 3] - grid[i][j - 3] - grid[i - 1][j - 2]\n",
    "                ans = max(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n =len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(1,m-1):\n",
    "            for j in range(1,n-1):\n",
    "                sum1 = grid[i-1][j-1]+grid[i-1][j]+grid[i-1][j+1]\n",
    "                sum2 = grid[i][j]\n",
    "                sum3 = grid[i+1][j-1]+grid[i+1][j]+grid[i+1][j+1]\n",
    "                res = max(res,sum1+sum2+sum3)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        ans = float('-inf')\n",
    "        for i in range(r - 2):\n",
    "            for j in range(c - 2):\n",
    "                v = grid[i][j] + grid[i][j + 1] + grid[i][j + 2] + grid[i + 1][j + 1] + grid[i + 2][j + 1] + grid[i + 2][j] + grid[i + 2][j + 2]\n",
    "\n",
    "                ans = max(ans, v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] + grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1] for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        result, m, n = 0, len(grid), len(grid[0])\n",
    "        for i in range(1, m-1):\n",
    "            cur = sum(grid[i-1][:2]) + sum(grid[i+1][:2])\n",
    "            for j in range(1, n-1):\n",
    "                cur += grid[i-1][j+1] + grid[i+1][j+1]\n",
    "                result = max(result, cur + grid[i][j])\n",
    "                cur -= grid[i-1][j-1] + grid[i+1][j-1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid) - 1):\n",
    "            for j in range(1, len(grid[0]) - 1):\n",
    "                ans = max(sum(grid[i - 1][j - 1 : j + 2]) + sum(grid[i + 1][j - 1 : j + 2]) + grid[i][j], ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "OFFSETS = [[0,0],[1,0],[2,0],[1,1],[0,2],[1,2],[2,2]]\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        return max(\n",
    "            sum(grid[row+dy][col+dx] for dx,dy in OFFSETS)\n",
    "            for row in range(rows-2)\n",
    "            for col in range(cols-2)\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def getPos(self, i,j) :\n",
    "        return [[i+0,j+0], [i+0,j+1],[i+0,j+2],[i+1,j+1],[i+2,j+0],[i+2,j+1],[i+2,j+2]]\n",
    "\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        # n = len(grid)\n",
    "        # max = 0\n",
    "        # for i in range(n-2):\n",
    "        #     for j in range(n-2):\n",
    "        #         print(i,j)\n",
    "        #         tmp =  [grid[p[0]][p[1]] for p in self.getPos(i,j)]\n",
    "        #         if max < sum(tmp): max = sum(tmp)\n",
    "        # return max\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        for i in range(2,m):\n",
    "            cur=0\n",
    "            #枚举行数\n",
    "            for j in range(2,n):\n",
    "                #枚举列数\n",
    "                cur=grid[i-2][j-2]+grid[i-2][j-1]+grid[i-2][j]+grid[i-1][j-1]+grid[i][j-2]+grid[i][j-1]+grid[i][j]\n",
    "                ans=max(cur,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                tmp = grid[i][j] + grid[i][j+1] + grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]\n",
    "                ans = max(ans, tmp)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, g: List[List[int]]) -> int:\n",
    "        m,n=len(g),len(g[0])\n",
    "        ans=0\n",
    "        for i in range(1,m-1):\n",
    "            for j in range(1,n-1):\n",
    "                ans=max(ans,g[i-1][j-1]+g[i-1][j]+g[i-1][j+1]+g[i][j]+g[i+1][j-1]+g[i+1][j]+g[i+1][j+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        res, m, n = 0, len(grid), len(grid[0])\n",
    "        for i in range(1, m - 1):\n",
    "            for j in range(1, n - 1):\n",
    "                x = sum(grid[i - 1][j-1:j+2]) + grid[i][j] + sum(grid[i+1][j-1:j+2])\n",
    "                res = max(res, x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(m - 2):\n",
    "            for j in range(n - 2):\n",
    "                res = 0\n",
    "                for k in range(3):\n",
    "                    for l in range(3):\n",
    "                        res += grid[i + k][j + l]\n",
    "                res -= grid[i + 1][j] + grid[i + 1][j + 2]\n",
    "                ans = max(ans, res)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        summ=0\n",
    "        for i in range(0,len(grid)-2):\n",
    "            for j in range(0,len(grid[0])-2):\n",
    "                temp=grid[i][j]+grid[i+1][j+1]+grid[i+2][j+2]+grid[i][j+1]+grid[i][j+2]+grid[i+2][j]+grid[i+2][j+1]\n",
    "                summ=max(summ,temp)\n",
    "        return summ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        ans=-inf\n",
    "        for i in range(1,n-1):\n",
    "            for j in range(1,m-1):\n",
    "                res=grid[i][j]+grid[i-1][j]+grid[i-1][j-1]+grid[i-1][j+1]+grid[i+1][j]+grid[i+1][j-1]+grid[i+1][j+1]\n",
    "                ans=max(ans,res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        tar=[(0,0),(0,1),(0,2),(1,1),(2,0),(2,1),(2,2)]\n",
    "        \n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res=0\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                s=0\n",
    "                for x,y in tar:\n",
    "                    s+=grid[i+x][j+y]\n",
    "                res=max(res,s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n =len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(1,m-1):\n",
    "            for j in range(1,n-1):\n",
    "                sum1 = grid[i-1][j-1]+grid[i-1][j]+grid[i-1][j+1]\n",
    "                sum2 = grid[i][j]\n",
    "                sum3 = grid[i+1][j-1]+grid[i+1][j]+grid[i+1][j+1]\n",
    "                res = max(res,sum1+sum2+sum3)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)# m行\n",
    "        n = len(grid[0]) # n列\n",
    "        ans= 0\n",
    "        for i in range(0,m-3+1): #\n",
    "            for j in range(0,n-3+1):\n",
    "                ans = max(ans,sum(grid[i][j:j+3])+sum(grid[i+2][j:j+3])+grid[i+1][j+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        _max = 0\n",
    "        for i in range(1,m-1):\n",
    "            for j in range(1,n-1):\n",
    "                _max = max(_max, sum(grid[i-1][j-1:j+2]) + grid[i][j] + sum(grid[i+1][j-1:j+2]))\n",
    "        return _max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max((grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] + grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]) for i in range(1, len(grid) - 1) for j in range(1, len(grid[0]) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(1, m-1):\n",
    "            for j in range(1, n-1):\n",
    "                sum_ = grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] + grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                ans = max(ans, sum_)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        def get_array(i, j):\n",
    "            nonlocal grid\n",
    "            res = []\n",
    "            if i + 2 >= len(grid) or j + 2 >= len(grid[0]):\n",
    "                return res\n",
    "            else:\n",
    "                res.append(grid[i][j])\n",
    "                res.append(grid[i][j + 1])\n",
    "                res.append(grid[i][j + 2])\n",
    "                res.append(grid[i + 1][j + 1])\n",
    "                res.append(grid[i + 2][j])\n",
    "                res.append(grid[i + 2][j + 1])\n",
    "                res.append(grid[i + 2][j + 2])\n",
    "                return res\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if not get_array(i, j):\n",
    "                    continue\n",
    "                else:\n",
    "                    res = max(res, sum(get_array(i, j)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        for r in range(1, m-1):\n",
    "            upSum = sum(grid[r-1][:3])\n",
    "            downSum = sum(grid[r+1][:3])\n",
    "            row = grid[r]\n",
    "            for c in range(1, n-1):\n",
    "                res = max(res, upSum + downSum + row[c])\n",
    "                if c < n-2:\n",
    "                    upSum += grid[r-1][c+2] - grid[r-1][c-1]\n",
    "                    downSum += grid[r+1][c+2] - grid[r+1][c-1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 遍历\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        return max(grid[i - 1][j - 1] + grid[i - 1][j] + grid[i - 1][j + 1] + grid[i][j] +\n",
    "                   grid[i + 1][j - 1] + grid[i + 1][j] + grid[i + 1][j + 1]\n",
    "                   for i in range(1, len(grid) - 1) for j in range(1, len(grid[i]) - 1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        max_sum = float('-inf')\n",
    "        for i in range(len(grid) - 2):\n",
    "            for j in range(len(grid[0]) - 2):\n",
    "                hourglass_sum = grid[i][j] + grid[i][j+1] + grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2]\n",
    "                max_sum = max(max_sum, hourglass_sum)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ans=0\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                c=grid[i][j]+grid[i][j+1]+grid[i][j+2]+grid[i+1][j+1]+grid[i+2][j]+grid[i+2][j+1]+grid[i+2][j+2]\n",
    "                ans=max(ans,c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        def check(r, c):\n",
    "            return grid[r][c] + sum(grid[r - 1][c - 1: c + 2]) + sum(grid[r + 1][c - 1: c + 2])\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        for r in range(1, R - 1):\n",
    "            for c in range(1, C - 1):\n",
    "                res = max(res, check(r, c))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n  = len(grid[0])\n",
    "        pre_sum = [[0]*(n+1) for _ in range(m)]\n",
    "        for r in range(m):\n",
    "            for j in range(1, n+1):\n",
    "                pre_sum[r][j] = pre_sum[r][j-1]+grid[r][j-1]\n",
    "\n",
    "        ans = 0\n",
    "        def get_max(i,j):\n",
    "            top=pre_sum[i][j+3] -  pre_sum[i][j]\n",
    "            mid = grid[i+1][j+1]\n",
    "            down = pre_sum[i+2][j+3] -  pre_sum[i+2][j]\n",
    "            return top+mid+down\n",
    "\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                ans = max(ans,get_max(i,j) )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        presum = [[0] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i].append(presum[i][-1] + grid[i][j])\n",
    "        result = 0\n",
    "        for i in range(2,m):\n",
    "            for j in range(2,n):\n",
    "                tmp = presum[i][j+1] - presum[i][j-2] + presum[i-1][j+1] - presum[i-1][j-2] + presum[i-2][j+1] - presum[i-2][j-2] - grid[i-1][j] - grid[i-1][j-2]\n",
    "                result = max(result, tmp)\n",
    "        return result \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n  = len(grid[0])\n",
    "        pre_sum = [[0]*(n+1) for _ in range(m)]\n",
    "        for r in range(m):\n",
    "            for j in range(1, n+1):\n",
    "                pre_sum[r][j] = pre_sum[r][j-1]+grid[r][j-1]\n",
    "\n",
    "        ans = 0\n",
    "        def get_max(i,j):\n",
    "            top=pre_sum[i][j+3] -  pre_sum[i][j]\n",
    "            mid = grid[i+1][j+1]\n",
    "            down = pre_sum[i+2][j+3] -  pre_sum[i+2][j]\n",
    "            return top+mid+down\n",
    "\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                ans = max(ans,get_max(i,j) )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        pr=[]\n",
    "        for x in grid:\n",
    "           c=[0] \n",
    "           for i in x:\n",
    "              c.append(c[-1]+i)\n",
    "           pr.append(c)\n",
    "        mx,n,m=0,len(grid),len(grid[0])   \n",
    "        for i in range(n-2):\n",
    "           for j in range(m-2):\n",
    "              c1=0\n",
    "              c1+=pr[i][j+3]-pr[i][j]\n",
    "              c1+=grid[i+1][j+1]\n",
    "              c1+=pr[i+2][j+3]-pr[i+2][j]\n",
    "              if c1>mx:\n",
    "                 mx=c1\n",
    "        return mx        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxSum(self, grid) :\n",
    "    ans = 0\n",
    "    m, n = len(grid), len(grid[0])\n",
    "    per_sum = [[0] * (n + 1) for _ in range(m)]\n",
    "    for i in range(m): per_sum[i][1] = grid[i][0]\n",
    "    for i in range(m):\n",
    "      for j in range(2, n + 1):\n",
    "        per_sum[i][j] = grid[i][j - 1] + per_sum[i][j - 1]\n",
    "    \n",
    "    for i in range(2, m):\n",
    "      for j in range(3, n + 1):\n",
    "        t = 0\n",
    "        t += per_sum[i][j] - per_sum[i][j - 3]\n",
    "        t += grid[i - 1][j - 2]\n",
    "        t += per_sum[i - 2][j] - per_sum[i - 2][j - 3]\n",
    "        ans = max(ans, t)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        presum = [[0] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i].append(presum[i][-1] + grid[i][j])\n",
    "        result = 0\n",
    "        for i in range(2,m):\n",
    "            for j in range(2,n):\n",
    "                tmp = presum[i][j+1] - presum[i][j-2] + presum[i-1][j+1] - presum[i-1][j-2] + presum[i-2][j+1] - presum[i-2][j-2] - grid[i-1][j] - grid[i-1][j-2]\n",
    "                result = max(result, tmp)\n",
    "        return result \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from pprint import pprint\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 首先创建一个二维的填充过的矩阵\n",
    "        prefixMat = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            # 计算行的前缀和\n",
    "            prefixRow = 0\n",
    "            for j in range(n):\n",
    "                prefixRow = prefixRow + grid[i][j]\n",
    "                prefixMat[i+1][j+1] = prefixRow + prefixMat[i][j+1]\n",
    "                # pprint(prefixMat)\n",
    "                # print(\"\\n\")\n",
    "        # 然后遍历二维矩阵，并且留出空间给子矩阵的size\n",
    "        res = -inf\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                subSum = prefixMat[i+3][j+3] - prefixMat[i][j+3] - prefixMat[i+3][j] + prefixMat[i][j]\n",
    "                hourglass = subSum - grid[i+1][j] - grid[i+1][j+2]\n",
    "                res = max(res, hourglass)\n",
    "        return res\n",
    "\n",
    "\n",
    "'''\n",
    "二维前缀和\n",
    "\n",
    "首先计算二维前缀和。计算方法：\n",
    " - 首先要计算每一行的前缀和\n",
    " - 其次对于当前位置的矩阵和，使用当前行的前缀和+上一行（保持j不变，i-1）的矩阵和\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PreFixSumMatrix:\n",
    "    def __init__(self, mat):\n",
    "        self.mat = mat\n",
    "        # 二维前缀和\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.pre[i + 1][j + 1] = self.pre[i][j + 1] + \\\n",
    "                    self.pre[i + 1][j] - self.pre[i][j] + mat[i][j]\n",
    "\n",
    "    def query(self, xa, ya, xb, yb):\n",
    "        # 二维子矩阵和查询，索引从 0 开始，左上角 [xa, ya] 右下角 [xb, yb]\n",
    "        return self.pre[xb + 1][yb + 1] - self.pre[xb +\n",
    "                                                   1][ya] - self.pre[xa][yb + 1] + self.pre[xa][ya]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre = PreFixSumMatrix(grid)\n",
    "        ans = 0\n",
    "        for i in range(1, m-1):\n",
    "            for j in range(1, n-1):\n",
    "                cur = pre.query(i-1, j-1, i+1, j+1) - grid[i][j-1]-grid[i][j+1]\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        prefixSum = [[0] * (n+1) for i in range(m+1)]\n",
    "        # 即首先计算每个点为右下角，00点为左上角，的所有矩形的元素的和\n",
    "        for i in range(m): \n",
    "            rowSum = 0\n",
    "            for j in range(n):\n",
    "                rowSum += grid[i][j]\n",
    "                prefixSum[i+1][j+1] = prefixSum[i][j+1] + rowSum\n",
    "        res = 0\n",
    "        # 然后每个地方都用二维前缀和的方式计算局部元素和即可\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                curSum = prefixSum[i+3][j+3] - prefixSum[i][j+3] - prefixSum[i+3][j] + prefixSum[i][j]\n",
    "                curSum = curSum - grid[i+1][j] - grid[i+1][j+2]\n",
    "                res = max(res, curSum)\n",
    "        return res\n",
    "\n",
    "\n",
    "'''\n",
    "二维前缀和\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                diff[i + 1][j + 1] = diff[i][j + 1] + diff[i + 1][j] - diff[i][j] + grid[i][j]\n",
    "        ret = 0\n",
    "        for i in range(2, m):\n",
    "            for j in range(2, n):\n",
    "                ret = max(ret, diff[i + 1][j + 1] - diff[i + 1][j - 2] - diff[i - 2][j + 1] + diff[i - 2][j - 2] - grid[i - 1][j] - grid[i - 1][j - 2])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from pprint import pprint\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        prefixSum = [[0] * (n+1) for i in range(m+1)]\n",
    "        for i in range(m): \n",
    "            rowSum = 0\n",
    "            for j in range(n):\n",
    "                rowSum += grid[i][j]\n",
    "                prefixSum[i+1][j+1] = prefixSum[i][j+1] + rowSum # 当前行的前缀+上一行的矩阵和\n",
    "                # pprint(prefixSum)\n",
    "                # print(\"\\n\")\n",
    "        res = 0\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                curSum = prefixSum[i+3][j+3] - prefixSum[i][j+3] - prefixSum[i+3][j] + prefixSum[i][j]\n",
    "                curSum -= grid[i+1][j] + grid[i+1][j+2]  # updating the indices to be consistent with Java version\n",
    "                res = max(res, curSum)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "二维前缀和\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        prefixSum = [[0] * (n+1) for i in range(m+1)]\n",
    "        for i in range(m): \n",
    "            rowSum = 0\n",
    "            for j in range(n):\n",
    "                rowSum += grid[i][j]\n",
    "                prefixSum[i+1][j+1] = prefixSum[i][j+1] + rowSum\n",
    "        res = 0\n",
    "        for i in range(m-2):\n",
    "            for j in range(n-2):\n",
    "                curSum = prefixSum[i+3][j+3] - prefixSum[i][j+3] - prefixSum[i+3][j] + prefixSum[i][j]\n",
    "                curSum -= grid[i+1][j] + grid[i+1][j+2]  # updating the indices to be consistent with Java version\n",
    "                res = max(res, curSum)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "二维前缀和\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSum(self, grid: List[List[int]]) -> int:\n",
    "        central_location = [ ]\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(1,m-1):\n",
    "            for j in range(1,n-1):\n",
    "                central_location.append( (i,j) )\n",
    "        max_val = 0\n",
    "        for i in central_location:\n",
    "            tmp_sum = sum( grid[i[0]-1][i[1]-1:i[1]+2] ) + grid[i[0]][i[1]]  + sum( grid[i[0]+1][i[1]-1:i[1]+2] )\n",
    "            if tmp_sum> max_val:\n",
    "                max_val = tmp_sum\n",
    "        return max_val"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
